package binary_tree.nowcoder.medium;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author bruin_du
 * @description 最近公共祖先
 * https://www.nowcoder.com/practice/70e00e490b454006976c1fdf47f155d9?
 * tpId=8&&tqId=11017&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 * @date 2022/5/6 22:03
 **/

public class LCA {
    //方法一
//    public int getLCA(int a, int b) {
//        int size = 1;
//        int n = 2;
//        while(size < a || size < b){
//            n *= 2;
//            size = n - 1;
//        }
//        TreeNode root = generateBTree(size,a,b);
//        return lca(root,a,b);
//    }
//    private int lca(TreeNode root,int a,int b){
//        if(root == null )
//            return -1;
//        if(root.val == a || root.val == b)
//            return root.val;
//        int left = lca(root.left,a,b);
//        int right = lca(root.right,a,b);
//        if(left < 0)
//            return right;
//        if(right < 0)
//            return left;
//        return root.val;
//    }
//    private TreeNode generateBTree(int size,int a,int b){
//        Queue<TreeNode> queue = new ArrayDeque<>();
//        TreeNode root = new TreeNode(1);
//        queue.offer(root);
//        int num = 1;
//        while(num < size){
//            TreeNode node = queue.poll();
//            TreeNode left = new TreeNode(++num);
//            node.left = left;
//            TreeNode right = new TreeNode(++num);
//            node.right = right;
//            if(size / 2 >= num) {
//                queue.offer(left);
//                queue.offer(right);
//            }
//        }
//        return root;
//    }

    //方法二
    //两个编号大的数 / 2,也就是它的父结点
    //直到两个结点值相等,就是LCA
    public int getLCA(int a,int b){
        while(a != b){
            if(a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }

    public static void main(String[] args) {
        LCA lca = new LCA();
        System.out.println(lca.getLCA(4,7));
    }
}
